This invention concerns the extraction of orthogonal transform coefficients from sequences of data. More specifically, this invention concerns processors for extracting sequency ordered, Walsh-Hadamard transform coefficients from serially presented data.
It is well known than any function having finite energy may be expressed as the sum of a series of orthogonal functions. In 1923 Joseph L. Walsh devised a complete set of orthogonal functions, now known as Walsh functions, which are especially useful for the representation of binary waveforms, Walsh functions, which are denoted by the expression EQU wal (s, t),
are binary functions having values of +1 and -1 in the unit interval. The sequency, s, of a Walsh function is defined herein as the number of times the value of that function changes sign within the unit interval (the term "sequency" is also used in the literature to denote one-half the number of sign changes in the unit interval). The sequency of a Walsh function may be seen to be somewhat analogous to the frequency of the more common sine or cosine functions.
A series of Walsh functions may be expressed in a matrix, known as a Hadamard matrix, in which elements are either +1 or -1 and in which the respective row vectors and the respective column vectors are mutually orthogonal. The values of the elements in a row or column of a Hadamard matrix represent the values of a Walsh function over sequential segments of the unit interval. Successive examination of the rows or columns of a Hadamard matrix yields a set of Walsh functions which are known as Hadamard functions denoted EQU H(n, t).
The natural order n, of a Hadamard function denotes the order in which that function is generated from a Hadamard matrix in the manner described above which is not the sequency order. Further discussion of the properties of Hadamard and Walsh functions and of algorithms for generating Hadamard matrices may be found in H. G. Harmuth, "Transmission of Information by Orthogonal Functions", Second Edition, Springer-Verlag, 1972.
The Walsh transform vector w.sub.a of a binary function vector f may be expressed in matrix notation as: EQU w.sub.a = [wal] f.sub.a ( 1)
where [wal] is a matrix whose rows are sequency ordered Walsh functions. The order of a Walsh transform, as defined herein, means the number of dimensions in the vector w.sub.a which may be seen to equal the rank of the matrix [wal].
Machines for generating the values of Walsh functions are well known in the computing arts. For example, U.S. Pat. No. 3,701,143 to Nacht and U.S. Pat. No. 3,795,864 to Fullton, Jr. describe digital circuits for generating Walsh functions. The Walsh transform of a binary data stream may be generated by performing the above indicated matrix multiplication using the Walsh functions generated by the above referenced circuits and a digital processor; for example see U.S. Pat. No. 3,859,515 to Radcliffe Jr. The process of generating Walsh transforms by direct matrix multiplication requires relatively large amounts of processing hardware and is somewhat time-consuming.
Machines for generating Walsh transforms using the process known as the "fast Hadamard transform" have been described in the prior art literature. These machines, two of which are described in U.S. Pat. Nos. 3,742,201 to Groginski and 3,792,355 to Miyata et al., generally operate in a pipeline mode: that is, a mode in which a sequence of input data is continuously processed to yield a continuous output stream of Walsh transform coefficients. The pipeline transform machines of the prior art act to produce naturally ordered Hadamard transform coefficients: that is, the transform coefficients of the input signal which correspond to matrix multiplication by a Hadamard or natually ordered matrix.
The process of Walsh-Hadamard transformation is especially useful in the conditioning of signals for efficient transmission over communication channels and in the recognition and extraction of information from optical and other imaging systems. Such applications of the Hadamard or Walsh transform are further discussed in the above-cited Harmuth reference and Groginski Patent. In many Walsh-Hadamard transform applications, it is desirable to process the transform coefficients of a binary data stream in a sequency order which has been shown to facilitate the extraction of information.
Prior art pipeline, Walsh-Hadamard transform generators incorporated recognition circuits to identify the sequency of the output transform coefficient signals. Such circuits, for example, those described in the above-referenced Groginski Patent, yielded sequency information for use in processing the output, transform signals but did not, without further storage and accessing means, yield sequency ordered Walsh-Hadamard transform coefficients.